{\magonebf 4.1 Priority Queues (priority\_queue)}

\decltwo priority\_queue K I 

{\bf 1. Definition}

An instance $Q$ of the parameterized data type \name\ is a
collection of items (type $pq\_item$). Every item contains a key from type 
$K$ and an information from the linearly ordered type $I$. $K$ is called the 
key type of $Q$ and $I$ is called the information type of $Q$. The number of 
items in $Q$ is called the size of $Q$. If $Q$ has size zero it is called the 
empty priority queue. We use $<k,i>$ to denote a $pq\_item$\ with key $k$ and 
information $i$.

\bigskip
{\bf 2. Creation}

a) \create Q {}

b) $\_priority\_queue${\tt <}$K,I,prio\_impl${\tt >} $Q$;

creates an instance \var\ of type \name\ and initializes it with the
empty priority queue. Variant a) chooses the default data structure
(cf.~4.1.4), and variant b) chooses class $prio\_impl$ as the 
implementation of the queue (cf.~section~9 for a list of possible
implementation parameters).


\bigskip
{\bf 3. Operations }

\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\+\op K        key {pq\_item\ it}    
                           {returns the key of item $it$.}
\+\nop                     {\precond $it$ is an item in \var.}
\smallskip
\+\op I        inf {pq\_item\ it}    
                           {returns the information of item $it$.}
\+\nop                     {\precond $it$ is an item in \var.}
\smallskip
\+\op pq\_item insert {K\ k,I\ i} 
                           {adds a new item $<k,i>$ to \var\ and returns $it$.}
\smallskip
\+\op pq\_item find\_min {}       
                           {returns an item with minimal information}
\+\nop                     {(nil if \var\ is empty)}
\smallskip
\+\op void     del\_item {pq\_item\ it} 
                           {removes the item $it$ from \var.}
\+\nop                     {\precond $it$ is an item in \var.}
\smallskip
\+\op K        del\_min {} 
                           {removes the item $it$ = \var.find\_min() from \var}
\+\nop                     {and returns the key of $it$.}
\+\nop                     {\precond \var\ is not empty.}
\smallskip
\+\op void     decrease\_inf {pq\_item\ it,\ I\ i} 
                           {makes i the new information of item $it$}
\+\nop                     {\precond $it$ is an item in \var\ and $i$}
\+\nop                     {is not larger then $inf(it)$.}
\smallskip
\+\op void     change\_key {pq\_item\ it,\ K\ k} 
                           {makes k the new key of item $it$}
\+\nop                     {\precond $it$ is an item in \var.}
\smallskip
\+\op void     clear {}        
                           {makes \var\ the empty priority queue }
\smallskip
\+\op bool     empty {} 
                           {returns true, if \var\ is empty, false otherwise}
\smallskip
\+\op int      size  {}
                           {returns the size of \var.}


\bigskip
{\bf 4. Implementation}

Priority queues are implemented by Fibonacci heaps ([FT84]. Operations insert, 
del\_item, del\_min take time $O(\log n)$, find\_min, decrease\_inf, 
key, inf, empty take time $O(1)$ and clear takes time $O(n)$, where $n$ is the 
size of \var. The space requirement is $O(n)$.


\bigskip
{\bf 5. Example}

Dijkstra's Algorithm (cf.~section 8.1)

